/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: tree.c 42 2009-11-13 18:50:14Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdarg.h>

#include "tree.h"

TreeNode * 
tree_node_create (TreeNode *parent, void *item, size_t children, ...)
{
  va_list args;
  TreeNode *tn, *child;
  size_t x;

  tn = malloc (sizeof (TreeNode));
  if (tn == NULL)
    return NULL;
  
  tn->item = item;
  tn->parent = parent;
  tn->children = list_create ();
  if (tn->children == NULL)
    {
      free (tn);
      return NULL;
    }

  va_start (args, children);
  for (x = 0; x < children; x++)
    {
      child = va_arg (args, TreeNode *);
      if (!tree_node_add_child (tn, child))
	{
	  list_destroy (tn->children, NULL);
	  free (tn);
	  return NULL;
	}
    }
  va_end (args);

  return tn;
}

void tree_node_destroy (TreeNode *node, destroy_func *dfunc, int dchildren)
{
  TreeNode *child;
      
  while (list_size (node->children) > 0)
    {
      child = list_remove_first (node->children);  
      if (dchildren)
	tree_node_destroy (child, dfunc, 1);
      else
	child->parent = NULL;
    }
  
  list_destroy (node->children, NULL);

  if (dfunc != NULL)
    dfunc (node->item);

  free (node);
}

int tree_node_add_child (TreeNode *node, TreeNode *child)
{
  if (list_insert_last (node->children, child))
    {
      child->parent = node;
      return 1;
    }
  else
    return 0;
}

int tree_node_remove_child (TreeNode *node, TreeNode *child)
{
  ListTraverser trav;
  TreeNode *cur;

  list_traverser_init (&trav, node->children);
  while ((cur = list_traverser_next (&trav)) != NULL)
    {
      if (cur == child)
	{
	  cur = list_traverser_remove (&trav);
	  cur->parent = NULL;

	  return 1;
	}
    }

  return 0;
}

List * tree_node_children (TreeNode *node)
{
  return node->children;
}

void tree_node_clear_children (TreeNode *node)
{
  TreeNode *child;
  while (list_size (node->children) > 0)
    {
      child = list_remove_first (node->children);
      child->parent = NULL;
    }

}

TreeNode * tree_node_find_root (TreeNode *node)
{
  TreeNode *root;

  root = node;
  while (root->parent != NULL)
    root = root->parent;

  return root;
}

size_t tree_node_height (TreeNode *node)
{
  TreeNode *cur;
  size_t max_height, cur_height;
  ListTraverser trav;

  if (list_size (node->children) == 0)
    return 1;

  max_height = 0;

  list_traverser_init (&trav, node->children);
  while ((cur = list_traverser_next (&trav)) != NULL)
    {
      cur_height = tree_node_height (cur);
      if (cur_height > max_height)
	max_height = cur_height;
    }

  return max_height + 1;
}

size_t tree_node_depth (TreeNode *node)
{
  if (node->parent == NULL)
    return 0;
  else
    return tree_node_depth (node->parent) + 1;
}

size_t tree_node_descendants (TreeNode *node)
{
  TreeNode *cur;
  size_t sum;
  ListTraverser trav;

  sum = 0;

  if (list_size (node->children) == 0)
    return 0;

  list_traverser_init (&trav, node->children);
  while ((cur = list_traverser_next (&trav)) != NULL)
    {
      sum++;
      sum += tree_node_descendants (cur);
    }

  return sum;
}

